import { ListNode } from "./utils";

export function removeNthFromEnd (head: ListNode | null, n: number): ListNode | null {

    if (!head) return head;
    const dummyHead = new ListNode();
    dummyHead.next = head;
    // dummyHead -> 1 -> 2 -> 3 -> 4 -> 5 -> null
    // 先找到倒数第 N+1 个
    // 使用双指针

    let fast = dummyHead;
    let low = dummyHead;

    // fast 先走 N+1 步
    let i = 0;
    while (i < n+1 && fast) {
        fast = fast.next!;
        i++;
    }
    if (i < n+1) return head;   // 没删除

    while (fast) {
        fast = fast.next!;
        low = low.next!;
    }
    // low 为 倒数第 N+1 个元素
    // 用 N+1 删除 N 个
    low.next = low.next!.next!;

    return dummyHead.next;
}